package leetcode.day_2021_03_15_2021_03_21;

/**
 * 64. 最小路径和
 * https://leetcode-cn.com/problems/minimum-path-sum/
 */
public class LeetCode0064 {

    public static int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];
        for (int row=1; row<rows; row++) {
            dp[row][0] = dp[row-1][0] + grid[row][0];
        }

        for (int col=1; col<cols; col++) {
            dp[0][col] = dp[0][col-1] + grid[0][col];
        }

        for (int row=1; row<rows; row++) {
            for (int col=1; col<cols; col++) {
                dp[row][col] = Math.min(dp[row][col-1], dp[row-1][col]) + grid[row][col];
            }
        }
        return dp[rows-1][cols-1];
    }

    public static void main(String[] args) {
        int[][] arr = {{1,3,1}, {1,5,1}, {4,2,1}};
        int[][] arr2 = {{1,2,3}, {4,5,6}};
        System.out.println(minPathSum(arr2));
    }
}
